ABBA [DP]
ABBA [DP]
2019牛客多校 第一场 E
题目来源：Nowcoder
分析
我们可以把这个题目看作一个已经拥有\(n\)个AB和\(m\)个BA，把它放入一个数组的过程。那么，题目即为要求有多少种放法。
这个题目的主要限制在于AB中的A一定先于B放入，BA同理。那么，我们可以发现，已放置的A和B的放置顺序对答案没有影响。即，只有“是否已放置”有影响，“放置在哪里”没有影响。那么，很明显，这道题便是一个DP了。我们使用dp[i][j]记录答案，其中i是放置了多少个A，j是放置对了多少个B。那么，很明显，我们需要满足以下两个条件：
- \(i \leq n + j\);
- \(j \leq m + i\).
在以上两个条件下进行状态转移即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <iostream>
#include <algorithm>
#define MAXN 1010
#define MOD 1000000007
using namespace std;
long long dp[2 * MAXN][2 * MAXN];
int main()
{
int n, m;
while (cin >> n >> m)
{
for (int i = 0; i<=n+m; i++)
for (int j = 0; j<=n+m; j++)
dp[i][j] = 0;
dp[0][0] = 1;
for (int i = 0; i<=n + m; i++)
for (int j = 0; j<=m + n; j++)
{
if (i < n + j)
dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD;
if (j < m + i)
dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD;
}
cout << dp[n+m][n+m] << endl;
}
}
|